from random import choice

class TicTacToeBoard:

    def __init__(self):
        self.board = (['N'] * 3, ['N'] * 3, ['N'] * 3)
                                      
    def print_board(self):
        print(self.board[0][0] + "|" + self.board[1][0] + "|" + self.board[2][0])
        
        print(self.board[0][1] + "|" + self.board[1][1] + "|" + self.board[2][1])
        
        print(self.board[0][2] + "|" + self.board[1][2] + "|" + self.board[2][2])
        
    def copy_board(self, board):
        for i in list(range(3)):
            for j in list(range(3)):
                self.board[i][j] = board.board[i][j]
        
    def play_square(self, col, row, val):
        self.board[col][row] = val

    def get_square(self, col, row):
        return self.board[col][row]

    def full_board(self):
        for i in list(range(3)):
            for j in list(range(3)):
                if(self.board[i][j] == 'N'):
                    return False

        return True
    
    #if there is a winner this will return their symbol (either 'X' or 'O'),
    #otherwise it will return 'N'
    def winner(self):
        #check the cols
        for col in list(range(3)):
            if(self.board[col][0] != 0 and self.board[col][0] == self.board[col][1] and self.board[col][0] == self.board[col][2]):
                return self.board[col][0]
        #check the rows
        for row in list(range(3)):
            if(self.board[0][row] != 0 and self.board[0][row] == self.board[1][row] and self.board[0][row] == self.board[2][row]):
                return self.board[0][row]
        #check diagonals
        if(self.board[0][0] != 0 and self.board[0][0] == self.board[1][1] and self.board[0][0] == self.board[2][2]):
            return self.board[0][0]
        if(self.board[2][0] != 0 and self.board[2][0] == self.board[1][1] and self.board[2][0] == self.board[0][2]):
            return self.board[2][0]
        return 'N'

def make_simple_cpu_move(board, cpuval):
    for i in list(range(3)):
        for j in list(range(3)):
            if(board.get_square(i, j) == 'N'):
                board.play_square(i, j, cpuval)
                return True
    return False

'''
Minimax algorithm which contains the alpha-beta pruning
'''
def make_minimax_cpu_move(board, cpuval, humanval):
    
    actions = {1:[], 0:[], -1:[]}
    for i in list(range(3)):
        for j in list(range(3)):
            if(board.get_square(i, j) == 'N'):
                new_board = TicTacToeBoard()
                new_board.copy_board(board)
                new_board.play_square(i, j, cpuval)
                actions[min_value(new_board, cpuval, humanval, -2, 2)].append([i, j])

    if actions[1] != []:
        i, j = choice(actions[1])
    elif actions[0] != []:
        i, j = choice(actions[0])
    else:
        i, j = choice(actions[-1])
        
    if(board.get_square(i, j) == 'N'):
        board.play_square(i, j, cpuval)
        return True
    return False

def min_value(board, cpuval, humanval, alph, bet):
    if board.winner() == cpuval:
        return 1
    elif board.winner() == humanval:
        return -1
    elif board.winner() == 'N':
        if board.full_board():
            return 0
        else:
            val = 2
            for i in list(range(3)):
                for j in list(range(3)):
                    if(board.get_square(i, j) == 'N'):
                        new_board = TicTacToeBoard()
                        new_board.copy_board(board)
                        new_board.play_square(i, j, humanval)
                        
                        val = min(val, max_value(new_board, cpuval, humanval, alph, bet))
                        if(val <= alph):
                            return val
                        bet = min(bet, val)
            return val

def max_value(board, cpuval, humanval, alph, bet):
    if board.winner() == cpuval:
        return 1
    elif board.winner() == humanval:
        return -1
    elif board.winner() == 'N':
        if board.full_board():
            return 0
        else:
            val = -2
            for i in list(range(3)):
                for j in list(range(3)):
                    if(board.get_square(i, j) == 'N'):
                        new_board = TicTacToeBoard()
                        new_board.copy_board(board)
                        new_board.play_square(i, j, cpuval)
                        
                        val = max(val, min_value(new_board, cpuval, humanval, alph, bet))
                        if(val >= bet):
                            return val
                        alph = max(alph, val)
            return val

def play_cpu_first(board, humanval, cpuval):

    board.print_board()
    
    while(board.full_board() == False and board.winner() == 'N'):
        print("CPU Move")
        make_minimax_cpu_move(board, cpuval, humanval)
        board.print_board()

        if (board.full_board() or board.winner() != 'N'):
            break
        else:
            while(1):
                print("your move, pick a row (0-2)")
                row = int(input())
                print("your move, pick a col (0-2)")
                col = int(input())

                if(board.get_square(col, row) != 'N'):
                    print("square already taken!")
                else:
                    break

            board.play_square(col, row, humanval)
            board.print_board()
    return
    
def play_human_first(board, humanval, cpuval):

    board.print_board()
    
    while(board.full_board() == False and board.winner() == 'N'):
        print("your move, pick a row (0-2)")
        row = int(input())
        print("your move, pick a col (0-2)")
        col = int(input())

        if(board.get_square(col, row) != 'N'):
            print("square already taken!")
            continue
        else:
            board.play_square(col, row, humanval)
            if (board.full_board() or board.winner() != 'N'):
                break
            else:
                board.print_board()
                print("CPU Move")
                make_minimax_cpu_move(board, cpuval, humanval)
                board.print_board()
    return

def main():
    Board = TicTacToeBoard()
    play = 1
    
    while(play != 'X' and play != 'O'):
        print("select your piece (X or O)")
        play = str(input())

    if(play == 'X'):
        humanval = 'X'
        cpuval = 'O'
        play_human_first(Board, humanval, cpuval)
    if(play == 'O'):
        humanval = 'O'
        cpuval = 'X'
        play_cpu_first(Board, humanval, cpuval)

    print("\nFinal Result")
    Board.print_board()
    if(Board.winner() == 'N'):
        print("Cat game")
    elif(Board.winner() == humanval):
        print("You Win!")
    elif(Board.winner() == cpuval):
        print("CPU Wins!")

main()
            
